package com.tiny.work.leetcode;

import org.junit.Test;

public class searchInsert {

    public int result = 0;

    public int searchInsert(int[] nums, int target) {
        result = 0;
        if (nums == null || nums.length <= 0) {
            return result;
        }
        searchInsert(nums, target, 0, nums.length - 1);
        return result;
    }

    private void searchInsert(int[] nums, int target, int l, int r) {
        if ((l == 0 && nums[l] <= target)
            || (l > 0 && nums[l] >= target && nums[l - 1] < target)) {
            result = l;
        }
        if ((r == nums.length - 1 && nums[r] < target)
            || (r < nums.length - 1 && nums[r] < target && nums[r + 1] >= target)) {
            result = r + 1;
        }
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        if (nums[mid] < target) {
            searchInsert(nums, target, mid + 1, r);
        } else if (nums[mid] >= target) {
            searchInsert(nums, target, l, mid);
        }
    }


    @Test
    public void tsr() {
        int[] nums;
        nums = new int[]{1, 2, 3, 8, 8, 23};
        int result = searchInsert(nums, 8);
        assert result == 3;
        nums = new int[]{};
        result = searchInsert(nums, 8);
        assert result == 0;
        nums = new int[]{1};
        result = searchInsert(nums, 8);
        assert result == 1;
        nums = new int[]{1};
        result = searchInsert(nums, 1);
        assert result == 0;
        nums = new int[]{1, 1};
        result = searchInsert(nums, 1);
        assert result == 0;
        nums = new int[]{1, 1, 1};
        result = searchInsert(nums, 1);
        assert result == 0;
    }
}
